Writing scalable concurrent programs is a difficult task, because it requires reasoning about the interaction between different threads that may access the same objects. Therefore, present day software uses locks to control the synchronization required when objects are accessed by multiple threads. Unfortunately, the use of locks leads to several well known performance and software engineering problems. Coarse-grained locking results in poor program performance, while fine-grained locking requires careful reasoning about possible deadlocks and synchronization bottlenecks, thereby making program maintenance difficult.
“Transactional memory” is a concurrent programming tool that helps programmers write scalable concurrent programs using sequential code. With transactional memory, a programmer uses “transactions”, which are code sections that appear to be executed atomically, that is, the code sections are executed as if there is no interleaving of the steps of one transaction with another transaction. The synchronization required to achieve this atomicity is transparent to the programmer, leaving them only the responsibility of specifying what code should be executed atomically, and not how the atomicity should be achieved.
Transactional memory can be implemented in hardware as hardware transactional memory (HTM), for example by simple additions to the hardware cache mechanisms of existing processors. While this latter HTM implementation should support transactions very efficiently, it is not robust: that is, it only supports transactions up to a fixed size, and some transactions would never be able to complete successfully. Moreover, the limitations of an HTM implementation are architecture-specific, which makes writing correct portable programs a difficult task.
Software transactional memory (STM) implementations on the other hand, can compensate for most of the HTM limitations, but are less efficient than HTM. Lately, a hybrid transactional memory (HyTM) implementation has also been suggested. The HyTM implementation uses STM only when HTM fails, or if it is not supported at all. In general, it appears that no widely available transactional memory implementation solely in hardware will be available in the near future.
All recent STM implementations have a fundamental problem in that STM cannot guarantee atomicity of a transaction if an object is accessed concurrently by both transactional code and regular, non-transactional read and write operations. That is, the atomicity of a transaction may be compromised if some of the memory locations the transactional code accesses are also concurrently accessed by non-transactional code.
One way around this difficulty is to require the programmer to keep track of which objects may be accessed by both transactional and non-transactional code. However, this will only result in more error-prone concurrent programs, eliminating the software engineering benefits promised by transactional memory. On the other hand, although STM implementations keep improving, it is not likely that it would be practical to replace all regular memory accesses with their transactional version, at least not until an efficient and robust transactional memory that is implemented purely in hardware is available.